<!DOCTYPE html>
<html lang="en" dir="ltr">

<head>
  <meta name="generator" content="Hugo 0.82.1" />
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="description" content="动态规划(Dynamic Programming)#动态规划问题的解决思路#对于一个动态规划问题，对于输入 $I_n$ 求结果 $R_n$。 需要找到一个结构（或称为状态）S，有：
 可得的初始状态值，比如: $S_0$ 状态的递推关系: $S_n = f(S_{n-1})$ 状态到结果的映射关系: $R_n = g(S_n)$  问题: 最长递增子序列# 问题:   给定数组 arr，设长度为 n，输出 arr 的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
  示例 1  输入 [2,1,5,3,6,4,8,9,7]
输出 [1,3,4,8,9]
 示例 2  输入 [1,2,8,6,4]
输出 [1,2,4]
说明 其最长递增子序列有 3 个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
解题思路#这道题挺难的。不知道是否有人可以独自的解决。 这里说一个解决的方案。 动态规划问题的通用解题步骤:
  第一步: 求出状态 S
  第二步: 由状态 S 推出结果 R">
<meta name="theme-color" content="#FFFFFF"><meta property="og:title" content="" />
<meta property="og:description" content="动态规划(Dynamic Programming)#动态规划问题的解决思路#对于一个动态规划问题，对于输入 $I_n$ 求结果 $R_n$。 需要找到一个结构（或称为状态）S，有：
 可得的初始状态值，比如: $S_0$ 状态的递推关系: $S_n = f(S_{n-1})$ 状态到结果的映射关系: $R_n = g(S_n)$  问题: 最长递增子序列# 问题:   给定数组 arr，设长度为 n，输出 arr 的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
  示例 1  输入 [2,1,5,3,6,4,8,9,7]
输出 [1,3,4,8,9]
 示例 2  输入 [1,2,8,6,4]
输出 [1,2,4]
说明 其最长递增子序列有 3 个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
解题思路#这道题挺难的。不知道是否有人可以独自的解决。 这里说一个解决的方案。 动态规划问题的通用解题步骤:
  第一步: 求出状态 S
  第二步: 由状态 S 推出结果 R" />
<meta property="og:type" content="article" />
<meta property="og:url" content="http://example.org/docs/dynamic-programing/" /><meta property="article:section" content="docs" />



<title>Dynamic Programing | My Golang Book</title>
<link rel="manifest" href="/manifest.json">
<link rel="icon" href="/favicon.png" type="image/x-icon">
<link rel="stylesheet" href="/book.min.2bc2364a4a4b31f0ec1debecf0a8f90a840821f143dfe1ac6a0f7cbcbdcf64ac.css" integrity="sha256-K8I2SkpLMfDsHevs8Kj5CoQIIfFD3&#43;Gsag98vL3PZKw=">
<script defer src="/en.search.min.84ce9693e6c02d95376f29aeb794c11824d09ed0440f910f008e91e9ed0436e4.js" integrity="sha256-hM6Wk&#43;bALZU3bymut5TBGCTQntBED5EPAI6R6e0ENuQ="></script>
<!--
Made with Book Theme
https://github.com/alex-shpak/hugo-book
-->

  
</head>

<body dir="ltr">
  <input type="checkbox" class="hidden toggle" id="menu-control" />
  <input type="checkbox" class="hidden toggle" id="toc-control" />
  <main class="container flex">
    <aside class="book-menu">
      <div class="book-menu-content">
        
  <nav>
<h2 class="book-brand">
  <a href="/"><span>My Golang Book</span>
  </a>
</h2>


<div class="book-search">
  <input type="text" id="book-search-input" placeholder="Search" aria-label="Search" maxlength="64" data-hotkeys="s/" />
  <div class="book-search-spinner hidden"></div>
  <ul id="book-search-results"></ul>
</div>











  



  
  <ul>
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/introduction/" class="">Golang 介绍</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/installation/" class="">安装、准备开发环境</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/go-routine/" class="">并发处理 - Go 协程</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/workspace-module/" class="">管理Go模块</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/erro-handling/" class="">错误处理</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/resources/" class="">Golang 资源</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/statements/" class="">Go For语句</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/guidelines/" class="">Go 开发规范</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/logging/" class="">日志</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/data-init/" class="">Data Init</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/data-types/" class="">Data Types</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/debug/" class="">Debug</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/dynamic-programing/" class=" active">Dynamic Programing</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/ecosystem/" class="">Ecosystem</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/performance/" class="">Performance</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/struct-interface/" class="">Struct Interface</a>
  

        </li>
      
    
      
        <li>
          
  
  

  
    <a href="http://example.org/docs/struct-tags/" class="">Struct Tags</a>
  

        </li>
      
    
  </ul>















</nav>




  <script>(function(){var a=document.querySelector("aside.book-menu nav");addEventListener("beforeunload",function(b){localStorage.setItem("menu.scrollTop",a.scrollTop)}),a.scrollTop=localStorage.getItem("menu.scrollTop")})()</script>


 
      </div>
    </aside>

    <div class="book-page">
      <header class="book-header">
        
  <div class="flex align-center justify-between">
  <label for="menu-control">
    <img src="/svg/menu.svg" class="book-icon" alt="Menu" />
  </label>

  <strong>Dynamic Programing</strong>

  <label for="toc-control">
    
    <img src="/svg/toc.svg" class="book-icon" alt="Table of Contents" />
    
  </label>
</div>


  
  <aside class="hidden clearfix">
    
  
<nav id="TableOfContents">
  <ul>
    <li><a href="#动态规划问题的解决思路">动态规划问题的解决思路</a></li>
    <li><a href="#问题-最长递增子序列">问题: 最长递增子序列</a>
      <ul>
        <li><a href="#解题思路">解题思路</a></li>
      </ul>
    </li>
    <li><a href="#参照">参照</a></li>
  </ul>
</nav>



  </aside>
  
 
      </header>

      
      
  <article class="markdown"><h1 id="动态规划dynamic-programming">
  动态规划(Dynamic Programming)
  <a class="anchor" href="#%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92dynamic-programming">#</a>
</h1>
<h2 id="动态规划问题的解决思路">
  动态规划问题的解决思路
  <a class="anchor" href="#%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e9%97%ae%e9%a2%98%e7%9a%84%e8%a7%a3%e5%86%b3%e6%80%9d%e8%b7%af">#</a>
</h2>
<p>对于一个动态规划问题，对于输入 $I_n$ 求结果 $R_n$。
需要找到一个结构（或称为状态）S，有：</p>
<ul>
<li>可得的初始状态值，比如: $S_0$</li>
<li>状态的递推关系: $S_n = f(S_{n-1})$</li>
<li>状态到结果的映射关系: $R_n = g(S_n)$</li>
</ul>
<h2 id="问题-最长递增子序列">
  问题: 最长递增子序列
  <a class="anchor" href="#%e9%97%ae%e9%a2%98-%e6%9c%80%e9%95%bf%e9%80%92%e5%a2%9e%e5%ad%90%e5%ba%8f%e5%88%97">#</a>
</h2>
<ul>
<li>问题:</li>
</ul>
<blockquote>
<p>给定数组 arr，设长度为 n，输出 arr 的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）</p>
</blockquote>
<ul>
<li>示例 1</li>
</ul>
<p>输入
[2,1,5,3,6,4,8,9,7]</p>
<p>输出
[1,3,4,8,9]</p>
<ul>
<li>示例 2</li>
</ul>
<p>输入
[1,2,8,6,4]</p>
<p>输出
[1,2,4]</p>
<p>说明
其最长递增子序列有 3 个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）</p>
<h3 id="解题思路">
  解题思路
  <a class="anchor" href="#%e8%a7%a3%e9%a2%98%e6%80%9d%e8%b7%af">#</a>
</h3>
<p>这道题挺难的。不知道是否有人可以独自的解决。
这里说一个解决的方案。
动态规划问题的通用解题步骤:</p>
<ul>
<li>
<p>第一步: 求出状态 S</p>
</li>
<li>
<p>第二步: 由状态 S 推出结果 R</p>
</li>
<li>
<p>状态 S 的描述为：</p>
<ul>
<li>
<p>数组: lengthMinVal
每个长度对应的递增子序列最后一位的最小值。</p>
</li>
<li>
<p>Map: lengthIndexes
长度为 n 的递增子序列的最后一位值的索引
key: int, 长度
value: int[], 相同长度对应的多个值。</p>
</li>
</ul>
</li>
<li>
<p>S 的一个重要性质
S.lengthIndexes 中，长度 n 对应的的索引列表中，任何一个索引都可以找到至少一个长度为 n 的递增子序列。</p>
</li>
</ul>
<p><strong>举例说明:</strong>
对于数组[10, 20, 30, 1, 2, 3]
可以看到:
长度为 1 的递增子序列，有两个: [10], [1]，最小值是 1
长度为 2 的递增子序列，有两个: [10, 20], [1, 2]，位置 2 上的最小值是 2
长度为 3 的递增子序列，有两个: [10, 20, 30], [1, 2, 3]，位置 3 上的最小值是 3
对于状态 S，
S.lengthMinVal: [1, 2, 3]
S.lengthIndexes:
[1: [0, 3]]
[2: [1, 4]]
[3: [2, 5]]</p>
<ul>
<li>
<p>状态 $S_0$ 的初始值
S.lengthMinVal = arr[0]
S.lengthIndexes[1] = [0]</p>
</li>
<li>
<p>状态 S 的递推关系$f$:
已知 $S_{n-1}$。
如果 $input_n &gt; S_{n-1}.lengthMinVal.lastValue$<br>
$S_n.lengthMinVal.append(input_n)$
$S_n.lengthIndexes[len(S_n.lengthMinVal)] = [n]$
否者，
在$S_n.lengthMinVal$ 中从小到大找到第一个大于$input_n$的位置 i（可以用二分法），用$input_n$替换到这个位置上
$S_n.lengthIndexes[i+1].append(n)$</p>
</li>
<li>
<p>状态 S 到 R 的映射 g
S.lengthIndexes 的 key 是从 1 到 $len(S_n.lengthMinVal)$.
其 value 是一个索引列表。
按照要求：
从 $len(S_n.lengthMinVal)$ 到 1，依次：在 value 中，找到值满足以下条件:</p>
</li>
</ul>
<ol>
<li>index 小于上一个 index</li>
<li>值最小</li>
</ol>
<h2 id="参照">
  参照
  <a class="anchor" href="#%e5%8f%82%e7%85%a7">#</a>
</h2>
<ul>
<li><a href="https://www.nowcoder.com/questionTerminal/9cf027bf54714ad889d4f30ff0ae5481">牛客网</a></li>
</ul>
</article>
 
      

      <footer class="book-footer">
        
  <div class="flex flex-wrap justify-between">





</div>

 
        
      </footer>

      
  
  <div class="book-comments">

</div>
  
 

      <label for="menu-control" class="hidden book-menu-overlay"></label>
    </div>

    
    <aside class="book-toc">
      <div class="book-toc-content">
        
  
<nav id="TableOfContents">
  <ul>
    <li><a href="#动态规划问题的解决思路">动态规划问题的解决思路</a></li>
    <li><a href="#问题-最长递增子序列">问题: 最长递增子序列</a>
      <ul>
        <li><a href="#解题思路">解题思路</a></li>
      </ul>
    </li>
    <li><a href="#参照">参照</a></li>
  </ul>
</nav>


 
      </div>
    </aside>
    
  </main>

  
</body>

</html>












